/**
* 各种排序算法

**/
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define   N   20 // 设置排序数据个数

typedef struct _node {
  int data;
  struct _node *next;
}node;

// 创建一个无序单链表
node *create_data()
{
  srand( (unsigned)time( NULL ) ); // 初始化随机数种子
  
  int n = N; // 有N个元素
  node *start = NULL, *p;
  while (n--) {
    if ( NULL == (p = (node*)malloc(sizeof(node))) ) {
      exit(-1); // 分配内存失败,直接GG
    }
    p->data = rand() % 100; // 随机赋值
    p->next = start;
    start   = p;
  }
  
  return start;
}
// 打印单链表,忽略第一个元素,该元素不会拿来排序
void print_node(const char *str, node *p)
{
  printf("%s\n", str);
  p = p->next;//跳过第一个元素
  while (p != NULL) {
    printf("%d,", p->data);
    p = p->next;
  }
  printf("\n");
}
// 单链表快速排序
// 这个排序第一个元素被舍弃,因此不要在第一个元素里面放待排序数据
// 因为第一个元素用来保存链表头,不会改变指针,下面的结束条件也有关
void LinkQuickSort(node *head, node *tail)
{
  if (head->next == tail) {
    return; // 1. head->next=tail=NULL,2. head->next=tail=第二个元素
  }
  
  node *mid = head->next;
  node *p   = head;
  node *q   = mid;
  node *t   = mid->next;
  
  while (t != tail) {
    if (t->data < mid->data) { // 和每次的中间元素比较
      p = p->next = t;
    } else {
      q = q->next = t;
    }
    t = t->next;
  }
  p->next = mid;  // 把小于mid的放到mid元素左边
  q->next = tail; // 把大于mid的放到mid元素右边

  LinkQuickSort(head, mid); // 继续对左边排序
  LinkQuickSort(mid, tail); // 继续对右边排序
}

// 打印数组中的值
void print_array(const char *str, int *data, int n)
{
  int i;
  printf("%s\n", str);
  for (i=0;i<N;++i){
    printf("%d,", data[i]);
  }
  printf("\n");
}

// 数组的快速排序
void ArrayQuickSort(int *data, int m, int n)
{
  int i,j,k,t;
  /*
  for (i=0;i<N;++i){
    printf("%d,", data[i]);
  }
  printf("\n");
  */
  
  if (m < n) { // 如果左边位置小于右边位置,则还需要排序
    i = m;j = n+1;k = data[m];
    while (i < j) {
      for (++i; i<N ; ++i) {
        if (data[i] > k) {
          break; // 找到一个大于k的位置
        }
      }
      
      for (--j; j>m ; --j) {
        if (data[j] < k) {
          break; // 找到一个小于k的位置
        }
      }
      
      if (i < j) { // 如果i的位置小于j位置,则将小的放到左边,大的放到右边,及交换位置
        t       = data[i];
        data[i] = data[j];
        data[j] = t;
      }
    }
    t       = data[m];
    data[m] = data[j];
    data[j] = t; // 将选择的mid值进行交换
    
    ArrayQuickSort(data, m, j-1); // 找左边
    ArrayQuickSort(data, i,   n); // 找右边
  }
}

// 冒泡排序
void BubbleSort(int *data, int n)
{
  int i, j, t;
  for (i = 0; i < n; ++i) { // 每次冒泡都将一个最大值放到结尾
    for (j = 0; j < n-i; ++j) {
      if (data[j] > data[j+1]) {
        t         = data[j];
        data[j]   = data[j+1];
        data[j+1] = t;
      }
    }
  }
}

// 希尔排序0
void ShellSort0(int *data, int left,int right)
{
  int len = right-left+1, d = len, i, tmp;
  while (d > 1) {
    d = (d+1)/2;
    for (i=left;i<right+1-d;++i) {
      if (data[i+d] < data[i]) {
        tmp = data[i+d];
        data[i+d]= data[i];
        data[i]=tmp;
      }
    }
  }
}

// 希尔排序1
void ShellSort1(int *data,int len)
{
  int d = len,i,tmp;
  while (d > 1) {
    d = (d+1)/2;
    for (i=0;i<len-d;++i) {
      if (data[i+d] < data[i]) {
        tmp = data[i+d];
        data[i+d]= data[i];
        data[i]=tmp;
      }
    }
  }
}

int main(int argc, char *argv[])
{
  node *start = create_data();
  print_node("link data:", start);
  LinkQuickSort(start, NULL);
  print_node("LinkQuickSort sort:",start);
  // 上面是单链表的快速排序
  int i, data[N]; // 下面对数组进行排序
  for (i=0; i<N; ++i) { data[i] = rand() % 100; } // 随机赋值
  
  print_array("array data:", data, N);
  ArrayQuickSort(data, 0, N-1);
  print_array("ArrayQuickSort sort:", data, N);
  
  for (i=0; i<N; ++i) { data[i] = rand() % 100; } // 随机赋值
  print_array("array data:", data, N);
  BubbleSort(data, N);
  print_array("BubbleSort sort:", data, N);
  
  for (i=0; i<N; ++i) { data[i] = rand() % 100; } // 随机赋值
  print_array("array data:", data, N);
  ShellSort0(data, 0, N-1);
  print_array("ShellSort0 sort:", data, N);
  
  for (i=0; i<N; ++i) { data[i] = rand() % 100; } // 随机赋值
  print_array("array data:", data, N);
  ShellSort1(data, N);
  print_array("ShellSort1 sort:", data, N);
  
  return 0;
}
